
/////////////////////////////////////////////////////////////////////////////////
//
//  泛型编码，template 模板编程。 02 ： 排序
//
//
/////////////////////////////////////////////////////////////////////////////////

#include<iostream>

void sortInt1(int arr[], int len)
{
    int tmp,isChange;
    for (int i = 0; i < len-1;i++)
    {
        isChange = 0;
        for (int j = 0; j < len-1-i;j++)
        {
            if (arr[j] > arr[j+1] )
            {
                isChange = 1;
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }

        std::cout<< "seq "<<i<<": ";
        for (int j = 0; j < len;j++)
        {
            std::cout << arr[j] << " " ;
        }
        std::cout << std::endl;
        if(isChange == 0)
            break;
    }
}

void sortInt2(int arr[], int len)
{
    int tmp,m,isChange;
    m = len-1;
    isChange = 1;
    while(m>0 && isChange)
    {
        isChange = 0;
        for (int j = 0; j <m;j++)
        {
            if (arr[j] > arr[j+1] )
            {
                isChange = 1;
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
        m--;

        std::cout<< "seq "<< m <<": ";
        for (int j = 0; j < len;j++)
        {
            std::cout << arr[j] << " " ;
        }
        std::cout << std::endl;
        if(isChange == 0)
            break;
    }
}

// 新增 lastChangeIndex 记录最后发生交换的位置，减少外层循环次数
void sortInt3(int arr[], int len)
{
    int tmp,m,isChange,lastChangeIndex;
    m = len-1;
    isChange = 1;
    while(m>0 && isChange)
    {
        isChange = 0;
        lastChangeIndex = 0;
        for (int j = 0; j <m;j++)
        {
            if (arr[j] > arr[j+1] )
            {
                isChange = 1;
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                lastChangeIndex = j;
            }
        }
        m=lastChangeIndex;

        std::cout<< "seq "<< m <<": ";
        for (int j = 0; j < len;j++)
        {
            std::cout << arr[j] << " " ;
        }
        std::cout << std::endl;
        if(isChange == 0)
            break;
    }
}

int main()
{
    // char carray[] = "hiliangdy";

    int iarr[] = {5,2,3,1,9,7,8};
    int len = sizeof(iarr) / sizeof(iarr[0]);

    for (int i = 0; i < len;i++)
    {
        std::cout << iarr[i] << " " ;
    }
    std::cout << std::endl;
    sortInt3(iarr,len);
    for (int i = 0; i < len;i++)
    {
        std::cout << iarr[i] << " " ;
    }

    // system("pause");
    return EXIT_SUCCESS;
}
